Pyramid transition matrix

Time: O(A^B); Space: O(A^B); medium

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string.

We are allowed to place any color block C on top of two adjacent blocks of colors A and B, if and only if ABC is an allowed triple.

We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

Example 1:

Input: bottom = “BCD”, allowed = [“BCG”, “CDE”, “GEA”, “FFF”]

Output: True

Explanation:

  • We can stack the pyramid like this:

        A
   / \
  G   E
 / \ / \
B   C   D

  • We are allowed to place G on top of B and C because BCG is an allowed triple.

  • Similarly, we can place E on top of C and D, then A on top of G and E.

Example 2:

Input: bottom = “AABA”, allowed = [“AAA”, “AAB”, “ABA”, “ABB”, “BAC”]

Output: False

Explanation:

  • We can’t stack the pyramid to the top.

  • Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.

Constraints:

  • bottom will be a string with length in range [2, 8].

  • allowed will have length in range [0, 200].

  • Letters in all strings will be chosen from the set {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}.

1. DFS

[1]:

class Solution1(object):
    """
    Time: O((A^(B+1)-A)/(A-1)) = O(A^B), A is the size of allowed, B is the length of bottom
    Space: O((A^(B+1)-A)/(A-1)) = O(A^B)
    """
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool
        """
        def pyramidTransitionHelper(bottom, edges, lookup):

            def dfs(bottom, edges, new_bottom, idx, lookup):
                if idx == len(bottom)-1:
                    return pyramidTransitionHelper(''.join(new_bottom), edges, lookup)
                for i in edges[ord(bottom[idx])-ord('A')][ord(bottom[idx+1])-ord('A')]:
                    new_bottom[idx] = chr(i+ord('A'))
                    if dfs(bottom, edges, new_bottom, idx+1, lookup):
                        return True
                return False

            if len(bottom) == 1:
                return True

            if bottom in lookup:
                return False

            lookup.add(bottom)

            for i in range(len(bottom)-1):
                if not edges[ord(bottom[i])-ord('A')][ord(bottom[i+1])-ord('A')]:
                    return False
            new_bottom = ['A']*(len(bottom)-1)

            return dfs(bottom, edges, new_bottom, 0, lookup)

        edges = [[[] for _ in range(7)] for _ in range(7)]

        for s in allowed:
            edges[ord(s[0])-ord('A')][ord(s[1])-ord('A')].append(ord(s[2])-ord('A'))

        return pyramidTransitionHelper(bottom, edges, set())

[2]:

s = Solution1()

bottom = "BCD"
allowed = ["BCG", "CDE", "GEA", "FFF"]
assert s.pyramidTransition(bottom, allowed) == True

bottom = "AABA"
allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
assert s.pyramidTransition(bottom, allowed) == False